﻿#include <iostream>
#include <vector>
using namespace std;
#include <stack>
 // Definition for a binary tree node.
  struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  };
 
class Solution {
public:
    bool GetPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& path)
    {
        //深度遍历前序查找，顺便用栈记录路径
        if (root == nullptr) return false;
        path.push(root);
        // 遇到root结点先push⼊栈，因为root就算不是x，但是root可能是根->x路径中⼀个分⽀结点
        if (root == x) return true;
        //root !=x 去左右子树查找
        if (GetPath(root->left, x, path))
        {
            return true;
        }
        if (GetPath(root->right, x, path))
        {
            return true;
        }
        // 如果左右⼦树都没有x，那么说明上⾯⼊栈的root不是根->x路径中⼀个分⽀结点
        // 所以要pop出栈，回退，继续去其他分⽀路径进⾏查找
        path.pop();
        return false;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
    {
        stack<TreeNode*> pPath;
        stack<TreeNode*> qPath;
        GetPath(root, p, pPath);
        GetPath(root, q, qPath);
        //找交点
        while (pPath.size() != qPath.size())
        {
            //大的先走
            if (pPath.size() > qPath.size())
            {
                pPath.pop();
            }
            else
            {
                qPath.pop();
            }
        }
        //一起走
        while (pPath.top() != qPath.top())
        {
            pPath.pop();
            qPath.pop();
        }

        return pPath.top();
    }
};


// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
class Solution {
public:
    void _treeToDoublyList(Node* root, vector<Node*>& v)
    {
        if (root == nullptr) return;
        _treeToDoublyList(root->left, v);
        v.push_back(root);
        _treeToDoublyList(root->right, v);
    }
    Node* treeToDoublyList(Node* root)
    {
        if (root == nullptr) return root;
        vector<Node*> v;
        _treeToDoublyList(root, v);
        for (int i = 0; i < v.size() - 1; i++)
        {
            v[i]->right = v[i + 1];
            v[i + 1]->left = v[i];

        }
        v[0]->left = v[v.size() - 1];
        v[v.size() - 1]->right = v[0];
        return v[0];
    }
};


/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
public:
    void Inorder(Node* cur, Node*& prev)
    {
        //中序遍历
        if (cur == nullptr)
            return;
        Inorder(cur->left, prev);
        //left指向中序前一个，左变成前驱
        cur->left = prev;
        //中序前一个节点的右指向cur，右变成后继
        if (prev)
            prev->right = cur;

        prev = cur;
        Inorder(cur->right, prev);
    }
    Node* treeToDoublyList(Node* root)
    {
        if (root == nullptr) return nullptr;

        Node* prev = nullptr;
        Inorder(root, prev);

        //找头
        Node* head = root;
        while (head->left)
        {
            head = head->left;
        }
        //循环链表
        head->left = prev;
        prev->right = head;
        return head;
    }
};